package com.lans.linear;

import java.util.Iterator;

/**
 * @author: lans
 * @date: 2025/2/23
 * @name: 刘宇
 */
public class Stack <T> implements Iterable<T> {
    private class Node{
        private T item;
        private Node next;
        public Node(T item,Node next){
            this.item = item;
            this.next = next;
        }
    }
    @Override
    public Iterator<T> iterator() {
        return new MyIterator();
    }
    private class MyIterator implements Iterator<T> {

        private Node n = head;
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public T next() {
            Node node = n.next;
            n = n.next;
            return node.item;
        }
    }

    private Node head;
    private int N;
    public Stack(){
        head = new Node(null,null);
        N=0;
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return N==0;
    }
    //获取栈中的元素个数
    public int size(){
        return N;
    }
    //弹出栈顶元素 获取栈的第一个元素
    public T pop(){
        Node firstNode = head.next;
        if(firstNode==null){
            return null;
        }
        //删除第一个节点 第一个节点会因为JVM的垃圾回收机制回收空间
        head.next = head.next.next;
        N--;
        return firstNode.item;
    }
    //向栈中压入元素
    public void push(T t){
         Node firstNode = head.next;
         Node node = new Node(t,firstNode);
         head.next = node;
         N++;
    }





    public static void main(String[] args) {
//        Stack<String> stack = new Stack<String>();
//        stack.push("王嘉淼");
//        stack.push("刘宇");
//        stack.push("哈基米");
//        stack.push("缅因 耄耋");
//        stack.pop();
//        for(String str:stack){
//            System.out.println(str);
//        }
        boolean match = isMatch("((布置后无)");
        System.out.println(match);
    }
    public static boolean isMatch(String str){
        //1.扫描字符串
        Stack<String> stack = new Stack<String>();
        for(int i=0;i<str.length();i++){
            //2.从左向右依次获取每一个字符
            String current = str.charAt(i)+"";
            //3.判断当前字符串是否存在左括号
            if(current.equals("(")){
                //4.如果是左括号,则放入栈中去
                stack.push(current);
            }else if(current.equals(")")){
                //5.如果是右括号,则去弹出对应的左括号
                String s = stack.pop();
                //6.如果弹出来是空值,则表示该字符串不匹配
                if(s==null){
                    return false;
                }
            }
        }
        //7.如果字符串遍历结束,栈中依然还存在左括号,则表示字符串不匹配
        if(stack.size()==0){
            //8.字符串遍历结束,对应的有括号都能弹出左括号,并且栈中直至为null,表示匹配成功
            return true;
        }else{
            return false;
        }
    }
}